1. Field of the Invention
The invention relates to error correction codes, and more particularly to decoding error correction codes.
2. Description of the Related Art
Error correction codes are used for correcting data errors. Communication system data is often encoded into an error correction code before the data is transmitted by a transmitter. When a receiver receives the error correction code, the receiver can correct data errors generated during the transmission process to recover the original data by decoding the error correction code. Similarly, data storage system data is often encoded into an error correction code before the data is stored in a storage medium. When the data stored in the storage medium is damaged, the original data can also be recovered by decoding the error correction code. A Bose, Ray-Chaudhuri, and Hocquenghem (BCH) code and a Reed-Solomon (RS) code are familiar error correction codes. The BCH code is commonly used for error correction in flash memory storage, and the RS code is commonly used for error correction in optical storage media.
When a data storage system retrieves data from a storage medium, because the data is stored in an error correction code form, the data storage system must decode the error correction code form to recover the original data. Referring to FIG. 1, a flowchart of a conventional method 100 for decoding an error correction code is shown. The error correction code is assumed to be a BCH code for example. First, a decoding circuit receives the BCH code retrieved from a storage medium (step 102). The decoding circuit then calculates an error syndrome of the BCH code (step 104). The decoding circuit then determines whether the error syndrome is equal to zero (step 106). If so, the BCHcode has no errors, and no correction is required. Otherwise, the non-zero error syndrome indicates that the BCH code is erroneous. The decoding circuit therefore must correct the BCH code.
The decoding circuit first calculates a plurality of coefficients of an error locator polynomial of the BCH code according to the error syndrome (step 108). The coefficients is calculated via a loop, wherein each cycle of the loop generates one of the coefficients, and the coefficients are thereby sequentially generated from low-order-term coefficients to high-order-term coefficients. The loop continues until a highest-order-term coefficient is generated (step 110), so that an entire set of the coefficients are obtained to establish the error polynomial. The decoding circuit then performs a Chien search to determine a plurality of roots of the error locator polynomial (step 112). The roots of the error locator polynomial indicates the error bit locations in the BCH code. The decoding circuit therefore can correct the BCH code according to the roots of the error locator polynomial (step 114), and a recovered BCH code without errors is therefore obtained.
Referring to FIG. 2, a schematic diagram of timings for decoding an error correction code according to the conventional method 100 is shown. At time ta, the decoding circuit starts to calculate the error syndrome of the error correction code (step 202). Calculation of the error syndrome requires a time period T1. At time tb, the decoding circuit starts to calculate the coefficients of the error locator polynomial of the error correction code (step 204), and the calculation of the coefficients requires a time period T2. At time tc, the decoding circuit starts to perform a Chien search to determine roots of the error locator polynomial (step 206), and performing of the Chien search requires a time period T3. The entire decoding process of the error correction code therefore requires a total time period of (T1+T2+T3).
Decoding of an error correction code is a requisite process for a receiver of a communication system and a data storage system such as an optical disk drive or a flash memory controller. If the time period required by decoding of an error correction code is reduced, performance of the communication system or the data storage system is improved. It is difficult however, to reduce the time period T1 required by calculation of the error syndrome, the time period T2 required by calculation of the coefficients of the error locator polynomial, and the time period T3 required by performing of the Chien search. A method for decoding an error correction code with a reduced time period to improve the performance of a communication system or a data storage system is therefore required.